1. Introduction

Motivation

Efficiency

Data Structure Philosophy

Abstract Data Types

Data Structure

Problem

Algorithms

Properties of Algorithms

Analysis of Algorithms

2. Asymptotic Analysis

Introduction

Overview

Experimental Approach

Theoretical

Complexity Analysis

Random-Access Machine Model

Running Time

Example

s = 0
for i = 1 to n
	s = s + 1

Asymptotic Analysis

Asymptotic Analysis

Big-O Notation

Screenshot

Big-Omega Notation f(n) = \Omega(g(n)) \space \text{iff} \space \exists c, n_0 > 0 {s.t.} \forall n \ge n_0, 0 \le cg(n) \le f(n)

Screenshot

Big-Theta Notation f(n) = \Theta(g(n)) \space \text{iff} \space \exists c_1, c_2, n_0 > 0 \space \text{s.t.} \space 0 \le c_1g(n) \le f(n) \le c_2g(n), \forall n \ge n_0

Screenshot

Example

Small O and Omega

Sum and Product Rule O(f + g) = \max\{O(f), O(g)\} O(f \times g) = O(f) \times O(g)

Typical Growth Rates

Screenshot

Proof, Relative Growth Rates, Complexity Classes

**Prove that 2n+1 = O(n)

Determining Growth Rates

Binary Search


left = 0
right = length - 1

while (left <= right):
	mid = (left + right) // 2
	if (target == mid):
		we found it!
	else if (target < mid):
		right = mid - 1
	else:
		left = mid + 1

Complexity Classes

Screenshot

3. Arrays

Introduction

Definition

Access

Insertion

Screenshot

Deletion

Example - Insertion Sort

Insertion Sort

StepStateStarting From
04, 15, 7, 22, 3N/A
14, 15, 7, 22, 31
24, 7, 15, 22, 32
34, 7, 15, 22, 33
44, 7, 15, 3, 224
54, 7, 3, 15, 224
64, 3, 7, 15, 224
73, 4, 7, 15, 224
i = 1
while (i < length(A)):
	j = i
	while j > 0 and A[j-1] > A[j]:
		swap A[j], A[j-1]
		j--
	i++

Complexity Analysis

Example - Prefix Average

4. Lists

List ADT

List Interface

List Operations

Array Implementation

Addition

Screenshot

Removal

Screenshot

Space Performance

Growable Arrays

Overview

Amortized Time

Incremental Strategy

Doubling Strategy

5. Sets and Multimaps

Set ADT

Overview

Operations

Screenshot

Storing a Set

Generic Merging

Generic Merging

function genericMerge(A, B):
	S = []
	while (not A.isEmpty() and not B.isEmpty())
		a = first element of A
		b = first element of B
		if (a < b):
			aIsLess(a, S)
			A.remove(a)
		else if (b < a):
			bIsLess(b, S)
			B.remove(b)
		else:
			bothAreEqual(a, b, S)
			S.remove(b)
	while (not A.isEmpty()):
		a = first element of A
		aIsLess(a, S)
		A.remove(a)
	while (not B.isEmpty()):
		b = first element of B
		bIsLess(b, S)
		B.remove(b)
	return S

Performance

Example - Union

abA \cup B
00[]
01[2]
11[2,3]
22[2,3,5]
32[2,3,5,6]
33[2,3,5,6,10]
34[2,3,5,6,10,15]

Example - Subtraction

abA\setminus B
00[]
01[]
11[3]
22[3]
32[3,6]
33[3,6]
34[3,6]

Multimaps

Overview

Operations

Screenshot

6. Linked Lists

Singly Linked Lists

Overview

Insertion

Screenshot

Screenshot

Deletion

Screenshot

Doubly Linked Lists

Overview

Screenshot

Insertion between p and its successor

Deletion

7. Recursion

Recursion

Overview

Example - Factorial f(n) = \begin{cases}1 & \text{if} \space n=0 \\ n\cdot f(n-1) & \text{else}\end{cases}

English Ruler

Overview

function drawInterval(length):
	if (length > 0) then
		drawInterval(length - 1)
		draw line of given length
		drawInterval(length - 1)

Screenshot

Screenshot

Binary Search - Recursive

Screenshot

Reversing an Array

function reverseArray(A, i, j):
		if (i < j) then
			swap A[i], A[j]
			reverseArray(A, i+1, j-1)
		return

Tail Recursion

function iterativeReverseArray(A, i, j):
	while (i < j) do
		swap A[i], A[j]
		i++
		j--
	return

Computing Powers

Method 1

Method 2

function Power(x, n)
	if n == 0 then
		return 1
	if n is odd then
		y = Power(x, (n - 1) / 2)
		return x * y * y
	else
		y = Power(x, n / 2)
		return y * y

Binary Recursion - Fibonacci Numbers

Recursive Algorithm

function BinaryFib(k):
	if k == 1 then
		return k
	else
		return BinaryFib(k-1) + BinaryFib(k-2)

Screenshot

Linear Algorithm

function LinearFibonacci(n):
	if n == 1 then
		return (n, 0)
	else
		(i, j) = LinearFibonacci(n-1)
		return (i+j, i)

Towers of Hanoi

Fractals

8. Stacks

Stack ADT

Overview

Array-based Stack

Operation

Screenshot

Limitation

Performance

Linked List Stack

Operation

Performance

Limitations

Applications of Stacks

Applications of Stacks

Function Stack in the JVM

Screenshot

Evaluating Arithmetic Expressions

TokenOperand StackOperator Stack
N/A[][]
12[12][]
-[12][-]
3[12, 3][-]
*[12,3][-,*]
5[12,3,5][-,*]
+[12,15][-]
+[-3][+]
2[-1][]

9. Queues

Queue ADT

Overview

Applications of Queues

Queue Interface in Java

Screenshot

Array-Based Queue

Removing an Element

Circular Queue

Rear Index

Screenshot

Performance

Linked-List Queue

10. Sorting

Insertion Sort

Selection Sort

Overview

Example - Sort 4, 15, 7, 22, 3

Screenshot

Sorting Algorithms - Lower Bounds

Theorem 1 - Any sorting algorithm that exchanges adjacent elements requires \Omega(n^2) average time

Theorem 2 - No sorting algorithm based on key comparisons can possibly be faster than \Omega(n\log n)

Divide and Conquer

Merge Sort

Overview

Algorithm

function mergeSort(S):
	if S.size() > 1:
		(S1, S2) = partition(S, n/2)
		mergeSort(S1)
		mergeSort(S2)
		S = merge(S1, S2)
	return S

 function merge(A, B):
	 S = []
	 while (not A.isEmpty() and not B.isEmpty()):
		if (A.first().element() < B.first().element()):
			 S.addLast(A.remove(A.first()))
		else:
			S.addLast(B.remove(B.first()))
	while (not A.isEmpty()):
		S.addLast(A.remove(A.first()))
	while (not B.isEmpty()):
		S.addlast(B.remove(B.first()))
	return S

Screenshot Screenshot

Running Time

Recurrence Equation Analysis

Recurrence Equation Analysis - Merge Sort

Master Method

Quick Sort

Overview

function QUICKSORT(A, start, end):
	if (start < end):
		positionPivot = PARTITION(A, start, end)
		QUICKSORT(A, start, positionPivot - 1)
		QUICKSORT(A, positionPivot + 1, end)

Pivot Selection Strategies

  1. Pick the first element in A - may lead to the worst-case scenario
  2. Randomly select the pivot - generating a random number is a costly operation
  3. Median-of-three strategy - median of first, last and middle value of A

Partitioning Algorithm

  1. Swap the pivot with the last element in the array
  2. Initialise pointers i = 0 and j = n - 1
  3. Whilst the pointers do not cross, move i until A[i] \ge p, and move j until A[j] \le p. If i < j, then we swap values at pointers i, j. Continue until pointers meet.
  4. Swap back the pivot with the left pointer i
function PARTITION():

	pi, p = PIVOT(A, start, end)
	i = start, j = end - 1

	// swap pivot to the end
	SWAP(A, pi, end)
	
	while i <= j:
		while i <= j and A[i] < p:
			i++
		while i <= j and A[j] > p:
			j--
		if (i >= j) break
		SWAP(A, i, j)
		i++
		j--

	// swap pivot back
	SWAP(A, left, end)
	return i

Example - Partitioning Algorithm

Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot Screenshot

Running Time Analysis

public class QuickSort {

    private static int medianOfThree(int[] arr, int i, int j, int k) {
        int a = arr[i];
        int b = arr[j];
        int c = arr[k];
        if ((a <= b && b <= c) || (c <= b && b <= a)) {
            return j;
        } else if ((b <= a && a <= c) || (c <= a && a <= b)) {
            return i;
        } else {
            return k;
        }
    }

    private static int pivot(int[] arr, int start, int end) {
        int mid = start + (end - start) / 2;
        return medianOfThree(arr, start, end, mid);
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int partition(int arr[], int start, int end) {

        int pivotIndex = pivot(arr, start, end);
        int pivot = arr[pivotIndex];
        swap(arr, pivotIndex, end);
        int i = start;
        int j = end - 1;


        while (i <= j) {
            while (i <= j && arr[i] < pivot) i++;
            while (i <= j && arr[j] > pivot) j--;

            if (i >= j) break;

            swap(arr, i, j);
            i++;
            j--;
        }

        swap(arr, i, end);
        return i;
    }

    private static void quickSort(int arr[], int start, int end) {
        if (start < end) {
            int positionPivot = partition(arr, start, end);
            quickSort(arr, start, positionPivot - 1);
            quickSort(arr, positionPivot + 1, end);
        }
    }
}

Summary of Sorting Algorithms

Screenshot

Bucket Sort

Overview

Algorithm

function bucketSort(S)
	for each entry e in S whose key is k:
		remove e and insert it at the end of bucket B[k]
	for i = 0 to m-1:
		for each entry e in B[i]:
			remove(e) and insert it at the end of S

Running Time

Stable Sorting

Stable Sorting

Common Stable Sorting Algorithms

**Common Unstable Sorting Algorithms

Radix Sort

Overview

Example

Screenshot

Running Time

11. Priority Queues

Priority Queue ADT

Overview

Comparator ADT

Total Order Relation

Comparator ADT

Priority Queue Implementation

Method 1 - Unsorted List

Method 2 - Sorted List

Priority Queue Sorting

Overview

Algorithm

function PQ-Sort(S, C):
	P = priority queue with comparator C
	while (not S.isEmpty()):
		e = S.remove(S.first())
		P.insert(e, NULL)
	while (not P.isEmpty()):
		e = P.removeMin().getKey()
		S.addLast(e)

Relation to Selection Sort

Relation to Insertion Sort

12. Heaps

Heaps

Overview

Height of a Heap

Screenshot

Relation to Priority Queues

Screenshot

Insertion into a Heap

Methodology

Upheap

Screenshot

Example

Screenshot

Algorithm - Node based Binary Tree

/* Upheap operation */
function upHeap(curr):
	while (curr.parent != NULL and curr.val < curr.parent.val):
		SWAP(curr.val, curr.parent.val)
		curr = curr.parent

Removal from a Heap

Methodology

Screenshot

Down-heap

Screenshot

Example

Screenshot

Algorithm - Node based Binary Tree

/* Down Heap Operation */
function downHeap(curr):

	while (curr != NULL):

		// get the smaller node
		smallest = curr
		if (curr.left != NULL && curr.left.val < smallest.val):
			smallest = curr.left
		if (curr.right != NULL && curr.right.val < smallest.val):
			smallest = curr.right

		// heap property satisfied - exit immediately
		if (smallest == node): break
		
		SWAP(curr.val, smallest.val)
		curr = smallest
		

Array-based Heap Implementation

Overview

Screenshot

Heap-Sort

Overview

Algorithm

  1. Insert the elements to be sorted in a heap
  2. Call removeMin() n times

Heapify

for i = (n-1)/2 to 0:
	downHeap(i)
void heapify(int arr[], int n, int i) {
	int smallest = i;
	int l = 2*i+1;
	int r = 2*i + 2;
	if (l < n && arr[l] < arr[smallest])
		smallest = l;
	if (r < n && arr[r] < arr[smallest])
		smallest = r;
	if (smallest != i) {
		SWAP(arr, i, smallest)
		heapify(arr, n, smallest)
	}
}

Example

Screenshot

Heapify - Running Time

13. Maps

Map ADT

Overview

Map ADT

Simple List-Based Map

Overview

Screenshot

get(k) Algorithm:

function get(k):
	B = S.positions()
	while B.hasNext() do
		p = B.next()
		if p.element().getKey() == k then
			return p.element().getValue()
	return null

put(k,v) Algorithm:

function put(k,v):
	B = S.positions()
	while B.hasNext() do
		p = B.next()
		if p.element().getKey() == k then
			t = p.element().getValue()
			S.set(p, (k,v))
			return t
	S.addLast((k, v))
	size++
	return null

remove(k) Algorithm

function remove(k):
	B = S.positions()
	while B.hasNext() do
		p = B.next()
		if p.element().getKey() == k then
			t = p.element().getValue()
			S.remove(p)
			size--
			return t
	return null

Performance

14. Hash Tables

Hash Tables

Overview

Hash Function

Hash Codes

Overview

  1. For a data type represented by at most 32-bits (int, byte, short, char), take as a hash code the integer representation of its bits
  2. For strings and tuples of the form (a_0, a_1, \cdots, a_{n-1}) we can use a polynomial hash code

Polynomial Hash Code

Compression Functions

Division

Multiply, Add and Divide (MAD) h_2(y) = (ay + b) \bmod N

Resolving Collisions - Separate Chaining

Overview

Separate Chaining

Screenshot

Resolving Collisions - Open Addressing

Open Addressing

Linear Probing

Screenshot

Quadratic Probing

Screenshot

Double Hashing

Screenshot

Analysis

Basic Operations - Open Addressing

Deleting from Hash Table

Overview

Analysis

Running Time

15. Trees

Introduction to Trees

Trees

Terminology

Tree ADT

Linked List Trees

Tree Traversals

Pre-Order Traversal

function preOrder(v):
	visit(v)
	for each child w of v:
		preOrder(w)

Screenshot

Post-Order Traversal

function postOrder(v):
	for each child w of v:
		postOrder(w)
	visit(v)

Screenshot

Binary Trees

Binary Tree ADT

Linked List Structure for Binary Trees

Proper Binary Trees

In Order Traversal

function inOrder(v):
	if left(v) != NULL:
		inOrder(left(v))
	visit(v)
	if right(v) != NULL:
		inOrder(right(v))

Screenshot

Application - Arithmetic Expressions

Screenshot

Application - Decision Tree

Screenshot

Running Time Analysis

Common Running Times:

Sorting - Decision Trees

Decision Tree Proof

Proof that \log(n!) = \Theta(n \log n) \log(n!) = \log(1\times 2 \times \cdots \times (n-1) \times n) = \log 1 + \log 2 + \cdots + \log(n/2) + \cdots + \log(n) \ge 0 + 0 + ... + \log(n/2) + \cdots + \log(n/2) \ge (n/2) \times \log(n/2)

Conclusion

16. Binary Search Trees

Binary Search Trees

Overview

Ordered Map - Sorted Array Implementation

Binary Search Tree

BST Search

Algorithm

function TreeSearch(k, v):
	if T.isExternal(v)
		return v
	if k < key(v):
		return TreeSearch(k, left(v))
	else if k > key(v):
		return TreeSearch(k, right(v))
	else:
		return v

BST Insert

Algorithm

function insertBST(k, v):

	// search for the place to insert
	parent = NULL
	curr = T.root
	while (curr != NULL):
		if k == curr.val().getKey():
			curr.val().setValue(v)
			return
		else if k < curr.val().getKey():
			parent = curr
			curr = curr.left
		else:
			parent = curr
			curr = curr.right

	// by now, we know that curr is NULL
	if (k < parent.val().getKey()):
		parent.setLeft(new Node(k, v))
	else:
		parent.setRight(new Node(k, v))

Screenshot

Screenshot

BST Delete

Algorithm

/* Helper Function */
function maxValue(curr):
	if curr.right != NULL:
		return maxValue(curr.right)
	return curr.val

/* Main Function */
function deleteBST(curr, key):
	if curr == NULL: return curr

	if key < curr.val:
		curr.left = deleteBST(curr.left, key)
	else if key > curr.val:
		curr.right = deleteBST(curr.right, key)
	else:
		// case 1
		if curr.left == NULL && curr.right == NULL:
			return NULL
		// case 2a
		else if curr.left != NULL && curr.right == NULL:
			return curr.left
		// case 2b
		else if curr.left == NULL && curr.right != NULL:
			return curr.right
		// case 3
		else:
			max = maxValue(curr.left)
			curr.left = deleteBST(curr.left, max)
			curr.val = max
	return curr

Screenshot Screenshot

Performance

Performance

17. AVL Trees

AVL Trees

Overview

Height of an AVL Tree

Insertion

Overview

Single Rotation - Example

Screenshot Screenshot

Trinode Restructuring

Screenshot

More Examples

Screenshot Screenshot Screenshot Screenshot Screenshot

Deletion

Overview

Algorithm

Screenshot

Time Complexities

Running times

18. Skip Lists

Skip Lists

Motivation

Skip Lists

Description

Screenshot

Search

Algorithm

Example

Screenshot

Insertion

Algorithm

Example

Screenshot

Deletion

Algorithm

Example

Screenshot

Implementation

Overview

Height, Space Usage, Running Time

Height

Space Usage

Running Time

19. Graphs

Introduction to Graphs

Graphs

Edge Types

Applications

Terminology

Properties

Complete Graph

Graph ADT

Graph Representation - Edge List

Overview

Screenshot

Performance

SpaceO(n+m)
incidentEdges(v)O(m)
getEdge(u,v)O(m)
insertVertex(o)O(1)
insertEdge(v,w,o)O(1)
removeVertex(v)O(m)
removeEdge(e)O(1)

Graph Representation - Adjacency List

Overview

Screenshot

Performance

SpaceO(n+m)
incidentEdges(v)O(deg(v))
getEdge(u,v)O(\min(\deg(u), deg(v)))
insertVertex(o)O(1)
insertEdge(v,w,o)O(1)
removeVertex(v)O(\deg(v))
removeEdge(e)O(1)

Remove Edge

Screenshot

Alternative Method:

Screenshot

Adjacency Map

Overview

Performance

SpaceO(n+m)
incidentEdges(v)O(\deg(v))
getEdge(u,v)Expected O(1)
insertVertex(o)O(1)
insertEdge(v,w,o)O(1)
removeVertex(v)O(\deg(v))
removeEdge(e)Expected O(1)

Adjacency Matrix

Overview

Screenshot

Performance

SpaceO(n^2)
incidentEdges(v)O(n)
getEdge(u,v)O(1)
insertVertex(o)O(n^2)
insertEdge(v,w,o)O(1)
removeVertex(v)O(n^2)
removeEdge(e)O(1)

Performance Summary

Screenshot

20. Depth First Search

Definitions

Traversals

Reachability Problems

Subgraphs

Connectivity

Screenshot

Trees and Forests

Spanning Trees and Forests

Depth First Search

Overview

Algorithm

function DFS(G, v):
	setLabel(v, VISITED)
	for all e in G.incidentEdges(v)
		if getLabel(e) == UNEXPLORED:
			w = opposite(v, e)
			if getLabel(w) == UNEXPLORED:
				setLabel(e, DISCOVERY)
				DFS(G, w)
			else:
				setLabel(e, BACK)	

Maze Traversal

Properties of DFS

  1. DFS(G, v) visits all the vertices and edges in the connected component of v
  2. Discovery edges labelled by DFS(G, v) form a spanning tree of the connected component of v

Running Time Analysis

Path Finding

function pathDFS(G, v, z):
	setLabel(v, VISITED)
	S.push(v)
	if (v == z):
		return S.elements()
	for all e in G.incidentEdges(v):
		if getLabel(e) == UNEXPLORED:
			w = opposite(v, e)
			if getLabel(w) == UNEXPLORED:
				setLabel(e, DISCOVERY)
				S.push(e)
				pathDFS(G, w, z)
				S.pop(e)
			else:
				setLabel(e, BACK)
	S.pop(v)

Backtracking

Screenshot

Cycle Finding

function cycleDFS(G, v, z):
	setLabel(v, VISITED)
	S.push(v)
	for all e in G.incidentEdges(v):
		if getLabel(e) == UNEXPLORED:
			w = opposite(v, e)
			S.push(e)
			if getLabel(w) == UNEXPLORED:
				setLabel(e, DISCOVERY)
				pathDFS(G, w, z)
				S.pop(e)
			else:
				T = Stack()
				repeat {
					T.push(o := S.pop())
				} until (o == w)
				return T.elements()
	S.pop(v)

All Connected Components

Screenshot

21. Breadth First Search

Breadth-First Search

Overview

Algorithm

function BFS(G, s):

	L0 = []
	L0.addLast(s)
	setLabel(s, VISITED)
	i = 0

	while not L{i}.isEmpty():
		L{i+1} = []
		for all v in L{i}.elements():
			for all e in G.incidentEdges(v):
				if getLabel(e) == UNEXPLORED:
					w = opposite(v, e)
					if getLabel(w) == UNEXPLORED:
						setLabel(e, DISCOVERY)
						setLabel(w, VISITED)
						L{i+1}.addLast(w)
					else:
						setLabel(e, CROSS)
		i++

Queue-Based Algorithm

function BFS(v, Q):
	Q.enqueue(v)
	v.visited = true
	while (!Q.empty()):
		Q.dequeue(v)
		for each vertex w adjacent to v:
			if (!w.visited):
				w.visited = true
				Q.enqueue(w)

Terminology

Screenshot

Properties

Screenshot

Running time

Applications

Screenshot

22. Directed Graphs

Digraphs

Overview

Properties

Application - Scheduling

Screenshot

Traversals

Screenshot

DAGs and Topological Ordering

Directed Acyclic Graphs

Topological Ordering

Screenshot

Topological Sorting

Screenshot

Algorithm - DFS

function topologicalDFS(G, v):
	setLabel(v, VISITED)
	for all e in G.outEdges(v):
		w = opposite(v, e)
		if getLabel(w) == UNEXPLORED:
			topologicalDFS(G, w)
	Label v with topological number n
	n--

Example

Screenshot Screenshot

Algorithm - using a Map

Screenshot Screenshot

23. Reachability

Reachability

Reachability

Strong Connectivity

Screenshot

Strongly Connected Components

Screenshot

Finding SCCs of a Graph

Transitive Closure

Overview

Screenshot

Computing the Transitive Closure

Reachability Matrix

Screenshot

T := A
repeat log n times:
	T := T | (T x T)